package problems.solved;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import problems.Problem;
import utils.CountingIterator;
import utils.Utils;

public class Problem50 extends Problem<Integer> {
	private static final int TARGET = 1000000;
	private static final int START = 92951;

	private final List<Integer> sieve = Utils.sieve(TARGET);

	public static void main(String[] args) {
		Problem50 problem50 = new Problem50();
		problem50.runTimed();
		problem50.printResult();
	}

	
	@Override
	public void run() {
		int[] results = new int[4];
		int maxPrimesInSum = 0;
		int result = 0;
		
		for (int i = 0; i < sieve.size(); i++) {
			int prime = sieve.get(i);
			for (int j = 0; j <= i && j < results.length; j++) {
				results[j] += prime;
				if (results[j] > TARGET) {
					setResult(result); // 997651
					return;
				}
				if (sieve.contains(results[j])) {
					int amount = i - j;
					if (amount > maxPrimesInSum) {
						maxPrimesInSum = amount;
						result = results[j];
					}
				}
			}
		}
	}

	@SuppressWarnings("unused")
	private void firstAttemptSlow() {
		long startTime = System.currentTimeMillis();
		int result = START;
		int maxPrimesInSum = primesInSum(START, 0);
		
		final int startIndex = sieve.indexOf(START) + 1;
		System.out.println("Starting at " + startIndex);
		
		ArrayList<Integer> list = new ArrayList<Integer>(sieve.subList(startIndex, sieve.size()));
		Collections.reverse(list);
		CountingIterator<Integer> iterator = new CountingIterator<Integer>(list);
		
		while (iterator.hasNext()) {
			if (iterator.getCount() % 100 == 0) {
				Utils.printProgress(iterator.getCount() + startIndex, sieve.size(), startTime);
			}

			int prime = iterator.next();
			assert Utils.isPrime(prime) : prime + " is not a prime";
			
			final int primesInSum = primesInSum(prime, maxPrimesInSum);
			if (primesInSum > maxPrimesInSum) {
				maxPrimesInSum = primesInSum;
				result = prime;
				System.out.printf("New result: %d (%d)%n", result, maxPrimesInSum);
			}
		}
		setResult(result); // 997651
	}

	private int primesInSum(int prime, int currentMax) {
		for (int i = 0; i < sieve.size(); i++) {
			final int result = doSublists(prime, currentMax, i);
			if (result != -1) {
				return result;
			}
		}
		return -1;
	}
	
	private int doSublists(int prime, int currentMax, int i) {
		for (int j = i + currentMax; j < sieve.size(); j++) {
			final List<Integer> consecutivePrimes = sieve.subList(i, j);
			int sum = (int) Utils.sumOfIntegers(consecutivePrimes);
			if (sum > prime) {
				return -1;
			}
			if (sum == prime) {
				return j-i;
			}
		}
		return -1;
	}

	
}
